﻿#ifndef __SS_MATCH_TREE_H__
#define __SS_MATCH_TREE_H__
#include <map>
#include <queue>
#include <iostream>
//字典树
//字符匹配用Aho-Corasick算法
namespace StarSeeker
{
	template<typename _Val>
	struct stdMatchNode
	{
		typedef _Val ValType;
		typedef stdMatchNode SelfType;
		typedef std::map<ValType, SelfType*> ChildMap;
		stdMatchNode() :pNext(NULL), key(), depth(0), isEnd(false) {};
		stdMatchNode(const ValType& val) :pNext(NULL), key(val), depth(0), isEnd(false){}
		~stdMatchNode();
		void AddChild(SelfType* pNode);
		SelfType* GetChild(ValType key);

		ChildMap childs;
		SelfType* pNext;
		SelfType* pPrev;
		ValType key;
		int depth;
		bool isEnd;
	};

	template<typename _Val>
	stdMatchNode<_Val>::~stdMatchNode()
	{
	}

	template<typename _Val>
	inline void stdMatchNode<_Val>::AddChild(SelfType* pNode)
	{
		if (pNode == NULL)
		{
			return;
		}
		typename ChildMap::iterator it = childs.find(pNode->key);
		if (it != childs.end())
		{
			return;
		}
		pNode->depth = depth+1;
		pNode->pPrev = this;
		childs[pNode->key] = pNode;
	}

	template<typename _Val>
	inline typename stdMatchNode<_Val>::SelfType * stdMatchNode<_Val>::GetChild(ValType key)
	{
		typename ChildMap::iterator it = childs.Find(key);
		if (it == childs.end())
		{
			return NULL;
		}
		return it->second;
	}

	template<typename _Val>
	class ssMatchTreeEx
	{
	public:
		typedef _Val ValType;
		typedef stdMatchNode<ValType> NodeType;
		typedef std::queue<NodeType*> NodeQueueType;

		ssMatchTreeEx();
		ssMatchTreeEx(const ssMatchTreeEx& trie);
		~ssMatchTreeEx();
		//预处理Aho-Corasick算法要用
		void InitNext();
		//复制
		void CopyFrom(const ssMatchTreeEx& trie);
		//插入一个字符串
		void Insert(const ValType* pBuf);

		int SearchKeyWord(const ValType* pBuf, size_t& len);
		const NodeType* SearchNode(const ValType* pBuf)const;
		size_t PrefixSearchCount(const ValType* pBuf)const;
		void Print();

	private:
#ifdef SS_MATCH_TREE_DEBUG
		void PrintNode(NodeType* pNode);
#endif
		//创建新节点
		NodeType* CreateNode();
		NodeType* CreateNode(const ValType& val);
		void DestroyNode(NodeType* pNode);
		void Init();
		NodeType* GetChildNode(NodeType* pPrev, const ValType& key);
		//比较两个节点的所有子节点的值是否相同
		bool CompareChilds(NodeType* pNode1, NodeType* pNode2);

		NodeQueueType	m_queue;
		NodeType*		m_pRoot;
		bool m_isInit;
	};


	template<typename _Val>
	inline void ssMatchTreeEx<_Val>::Init()
	{
		m_pRoot = CreateNode();
		m_pRoot->depth = -1;
		m_pRoot->pNext = NULL;
		m_pRoot->pPrev = m_pRoot;
#ifdef SS_MATCH_TREE_DEBUG
		m_pRoot->key = 0;
#endif

	}



	template<typename _Val>
	inline ssMatchTreeEx<_Val>::ssMatchTreeEx()
	{
		Init();
	}

	template<typename _Val>
	inline ssMatchTreeEx<_Val>::ssMatchTreeEx(const ssMatchTreeEx& trie)
	{
		Init();
	}

	template<typename _Val>
	ssMatchTreeEx<_Val>::~ssMatchTreeEx()
	{
		NodeType* pNode = NULL;
		NodeType* pNow = NULL;
		typename NodeType::ChildMap::iterator it;
		m_queue.push(m_pRoot);
		while (!m_queue.empty())
		{
			pNode = m_queue.front();m_queue.pop();
			it = pNode->childs.begin();
			for (; it != pNode->childs.end(); ++it)
			{
				pNow = it->second;
				m_queue.push(pNow);
			}
			DestroyNode(pNode);
		}
	}

	template<typename _Val>
	inline void ssMatchTreeEx<_Val>::InitNext()
	{
		NodeType* pNode = NULL;
		NodeType* pNext = NULL;
		NodeType* pNextX = NULL;
		NodeType* pNow = NULL;
		typename NodeType::ChildMap::iterator it;
		m_queue.push(m_pRoot);
		while (!m_queue.empty())
		{
			pNode = m_queue.front();m_queue.pop();
			it = pNode->childs.begin();
			for (; it != pNode->childs.end(); ++it)
			{
				pNow = it->second;
				if(pNode == m_pRoot)
				{
					pNow->pNext = m_pRoot;
				}
				else
				{
					pNext = pNode->pNext;
					while (pNext != NULL)
					{
						pNextX = GetChildNode(pNext, pNow->key);
						if (pNextX != m_pRoot)
						{
							pNow->pNext = pNextX;
							break;
						}

						pNext = pNext->pNext;
					}// while (pNext != NULL)

					if (pNext == NULL)
					{
						pNow->pNext = m_pRoot;
					}
				}
				m_queue.push(pNow);
			}
		}
		// 优化:节点和本节点的回朔节点 他们的子节点相同的要回朔到回朔节点的回朔节点
		// if(pNow->childs == pNow->pNext->childs)
		// {pNow->pNext =  pNow->pNext->pNext;}
		m_queue.push(m_pRoot);
		while (!m_queue.empty())
		{
			pNode = m_queue.front();m_queue.pop();
			it = pNode->childs.begin();
			for (; it != pNode->childs.end(); ++it)
			{
				pNow = it->second;
				pNext = pNow->pNext;
				if (CompareChilds(pNow, pNext))
				{
					pNow->pNext = pNext->pNext;
				}
				m_queue.push(pNow);
			}
		}
		m_isInit = true;
	}

	template<typename _Val>
	inline void ssMatchTreeEx<_Val>::Insert(const ValType * pBuf)
	{
		NodeType* pNode = m_pRoot;
		NodeType* pAddNode = NULL;
		for (size_t i = 0; pBuf[i] != 0; ++i)
		{
			//pNode = CreateNode(pBuf[i]);
			pAddNode = GetChildNode(pNode, pBuf[i]);
			if (pAddNode == m_pRoot)
			{
				pAddNode = CreateNode(pBuf[i]);
				if (pAddNode == NULL)
				{
					return;
				}
				pNode->AddChild(pAddNode);
				m_isInit = false;
			}
			pNode = pAddNode;
		}
		pNode->isEnd = true;

	}



	template<typename _Val>
	inline int ssMatchTreeEx<_Val>::SearchKeyWord(const ValType* pBuf, size_t& len)
	{
		if (!m_isInit)
		{
			InitNext();
		}
		NodeType* pNode = m_pRoot;
		NodeType* pNodeNext = m_pRoot;
		NodeType* pTNode = NULL;
		for (int i = 0; pBuf[i] != 0; ++i)
		{
			while (pNodeNext == m_pRoot && pNode != m_pRoot)
			{
				pNodeNext = GetChildNode(pNode, pBuf[i]);
				if (pNodeNext == m_pRoot && pNode != m_pRoot)
				{
					pNode = pNode->pNext;
				}
			}

			if (pNode == m_pRoot && pNodeNext == m_pRoot)
			{
				pNodeNext = GetChildNode(pNode, pBuf[i]);
			}

			if (pNodeNext->isEnd)
			{
				len = pNodeNext->depth +1;
				return i-pNodeNext->depth;
			}
			pTNode = pNodeNext;
			while (pTNode != m_pRoot)
			{
				if (pTNode->isEnd)
				{
					len = pTNode->depth+1;
					return i-pTNode->depth;
				}
				pTNode = pTNode->pNext;
			}

			pNode = pNodeNext;
			pNodeNext = m_pRoot;
		}

		return -1;

	}

	template<typename _Val>
	inline const typename ssMatchTreeEx<_Val>::NodeType* ssMatchTreeEx<_Val>::SearchNode(const ValType * pBuf) const
	{
		return NULL;
	}

	template<typename _Val>
	inline void ssMatchTreeEx<_Val>::Print()
	{
#ifdef SS_MATCH_TREE_DEBUG
		PrintNode(m_pRoot);
#endif
	}

	template<typename _Val>
	inline typename ssMatchTreeEx<_Val>::NodeType * ssMatchTreeEx<_Val>::GetChildNode(NodeType* pPrev, const ValType & key)
	{
		typename NodeType::ChildMap::iterator it = pPrev->childs.find(key);
		if (it == pPrev->childs.end())
		{
			return m_pRoot;
		}
		return it->second;
	}

	template<typename _Val>
	inline typename ssMatchTreeEx<_Val>::NodeType * ssMatchTreeEx<_Val>::CreateNode()
	{
		return new NodeType();
	}

	template<typename _Val>
	void ssMatchTreeEx<_Val>::DestroyNode(NodeType* pNode)
	{
		delete pNode;
	}

	template<typename _Val>
	inline typename ssMatchTreeEx<_Val>::NodeType * ssMatchTreeEx<_Val>::CreateNode(const ValType & val)
	{
		return new NodeType(val);
	}

	template<typename _Val>
	bool ssMatchTreeEx<_Val>::CompareChilds(NodeType* pNode1, NodeType* pNode2)
	{
		if (pNode1 == pNode2)
		{
			return true;
		}

		if (pNode1 == NULL)
		{
			return false;
		}

		if (pNode2 == NULL)
		{
			return false;
		}

		if (pNode1->childs.size() != pNode2->childs.size())
		{
			return false;
		}

		typename NodeType::ChildMap::iterator it1 = pNode1->childs.begin();
		typename NodeType::ChildMap::iterator it2 = pNode2->childs.end();
		for (; it1 != pNode1->childs.end(); ++it1)
		{
			it2 = pNode2->childs.find(it1->first);
			if (it2 == pNode2->childs.end())
			{
				return false;
			}
		}
		return true;
	}

#ifdef SS_MATCH_TREE_DEBUG
	template<typename _Val>
	void ssMatchTreeEx<_Val>::PrintNode(NodeType* pNode)
	{
		for (int i = 0; i <= pNode->depth; ++i)
		{
			std::cout << "-";
		}
		std::cout << "|key:" << pNode->key << "|depth:" << pNode->depth;
		if (pNode->pNext)
			std::cout << "|nextKey:" << pNode->pNext->key << "|nextDepth:" << pNode->pNext->depth;
		std::cout << "|\n";
		typename NodeType::ChildMap::iterator it = pNode->childs.begin();
		for (; it != pNode->childs.end(); ++it)
		{
			PrintNode( it->second );
		}
	}
#endif
}

#endif
